home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Internet Tools 1993 July / Internet Tools.iso / RockRidge / mail / mush-7.1.1 / malloc.c < prev    next >
Encoding:
C/C++ Source or Header  |  1990-05-02  |  10.6 KB  |  436 lines
  1. /*
  2.  * This is a slightly modified version of the malloc.c distributed with
  3.  * Larry Wall's perl 2.0 sources.  RCS and sccs information has been
  4.  * retained, but modified so that it will not actually affect checkin
  5.  * or checkout of this file if revision control is used for Mush.
  6.  *
  7.  * Other changes include:
  8.  *    Removal of the ASSERT macro and other code related to the
  9.  *    preprocessor definition "debug"
  10.  *
  11.  *    Replaced #include "perl.h" with #include "mush.h" (guess why)
  12.  *
  13.  *    Warning messages are now printed with the mush Debug macro,
  14.  *    that is, they are normally suppressed
  15.  *
  16.  *    Added a calloc() function, using mush's bzero()
  17.  *
  18.  * Also, the mush xfree() and free_vec() functions have been moved here.
  19.  */
  20.  
  21. #include "mush.h"
  22.  
  23. /*
  24.  * Compile this portion only if configured for INTERNAL_MALLOC
  25.  */
  26. #ifdef INTERNAL_MALLOC
  27. #ifdef SYSV
  28. #include <memory.h>
  29. #define bcopy(src,dst,len)    memcpy(dst,src,len)
  30. #endif /* SYSV */
  31. #define free xfree    /* rename free for mush purposes */
  32.  
  33. /* Begin modified perl malloc.c */
  34.  
  35. /* Header: malloc.c,v 2.0 88/06/05 00:09:16 root Exp
  36.  *
  37.  * Log:    malloc.c,v
  38.  * Revision 2.0  88/06/05  00:09:16  root
  39.  * Baseline version 2.0.
  40.  * 
  41.  */
  42.  
  43. #ifndef lint
  44. static char sccsid[] = "malloc.c    4.3 (Berkeley) 9/16/83";
  45. #endif /* !lint */
  46.  
  47. #define RCHECK
  48. /*
  49.  * malloc.c (Caltech) 2/21/82
  50.  * Chris Kingsley, kingsley@cit-20.
  51.  *
  52.  * This is a very fast storage allocator.  It allocates blocks of a small 
  53.  * number of different sizes, and keeps free lists of each size.  Blocks that
  54.  * don't exactly fit are passed up to the next larger size.  In this 
  55.  * implementation, the available sizes are 2^n-4 (or 2^n-12) bytes long.
  56.  * This is designed for use in a program that uses vast quantities of memory,
  57.  * but bombs when it runs out. 
  58.  */
  59.  
  60. /* I don't much care whether these are defined in sys/types.h--LAW */
  61.  
  62. #undef u_char
  63. #define u_char unsigned char
  64. #undef u_int
  65. #define u_int unsigned int
  66. #undef u_short
  67. #define u_short unsigned short
  68.  
  69. /*
  70.  * The overhead on a block is at least 4 bytes.  When free, this space
  71.  * contains a pointer to the next free block, and the bottom two bits must
  72.  * be zero.  When in use, the first byte is set to MAGIC, and the second
  73.  * byte is the size index.  The remaining bytes are for alignment.
  74.  * If range checking is enabled and the size of the block fits
  75.  * in two bytes, then the top two bytes hold the size of the requested block
  76.  * plus the range checking words, and the header word MINUS ONE.
  77.  */
  78. union    overhead {
  79.     union    overhead *ov_next;    /* when free */
  80.     struct {
  81.         u_char    ovu_magic;    /* magic number */
  82.         u_char    ovu_index;    /* bucket # */
  83. #ifdef RCHECK
  84.         u_short    ovu_size;    /* actual block size */
  85.         u_int    ovu_rmagic;    /* range magic number */
  86. #endif /* RCHECK */
  87.     } ovu;
  88. #define    ov_magic    ovu.ovu_magic
  89. #define    ov_index    ovu.ovu_index
  90. #define    ov_size        ovu.ovu_size
  91. #define    ov_rmagic    ovu.ovu_rmagic
  92. };
  93.  
  94. #define    MAGIC        0xff        /* magic # on accounting info */
  95. #define OLDMAGIC    0x7f        /* same after a free() */
  96. #define RMAGIC        0x55555555    /* magic # on range info */
  97. #ifdef RCHECK
  98. #define    RSLOP        sizeof (u_int)
  99. #else /* !RCHECK */
  100. #define    RSLOP        0
  101. #endif /* RCHECK */
  102.  
  103. /*
  104.  * nextf[i] is the pointer to the next free block of size 2^(i+3).  The
  105.  * smallest allocatable block is 8 bytes.  The overhead information
  106.  * precedes the data area returned to the user.
  107.  */
  108. #define    NBUCKETS 30
  109. static    union overhead *nextf[NBUCKETS];
  110. extern    char *sbrk();
  111.  
  112. #ifdef MSTATS
  113. /*
  114.  * nmalloc[i] is the difference between the number of mallocs and frees
  115.  * for a given block size.
  116.  */
  117. static    u_int nmalloc[NBUCKETS];
  118. #endif /* MSTATS */
  119.  
  120. char *
  121. malloc(nbytes)
  122.     register unsigned nbytes;
  123. {
  124.     register union overhead *p;
  125.     register int bucket = 0;
  126.     register unsigned shiftr;
  127.  
  128.     /*
  129.      * Convert amount of memory requested into
  130.      * closest block size stored in hash buckets
  131.      * which satisfies request.  Account for
  132.      * space used per block for accounting.
  133.      */
  134.     nbytes += sizeof (union overhead) + RSLOP;
  135.     nbytes = (nbytes + 3) &~ 3; 
  136.     shiftr = (nbytes - 1) >> 2;
  137.     /* apart from this loop, this is O(1) */
  138.     while (shiftr >>= 1)
  139.         bucket++;
  140.     /*
  141.      * If nothing in hash bucket right now,
  142.      * request more memory from the system.
  143.      */
  144.     if (nextf[bucket] == (union overhead *)0)    
  145.         morecore(bucket);
  146.     if ((p = (union overhead *)nextf[bucket]) == (union overhead *)0)
  147.         return (NULL);
  148.     /* remove from linked list */
  149.     if (*((int*)p) > 0x10000000)
  150.         Debug("Corrupt malloc ptr 0x%x at 0x%x\n",*((int*)p),p);
  151.     nextf[bucket] = nextf[bucket]->ov_next;
  152.     p->ov_magic = MAGIC;
  153.     p->ov_index= bucket;
  154. #ifdef MSTATS
  155.     nmalloc[bucket]++;
  156. #endif /* MSTATS */
  157. #ifdef RCHECK
  158.     /*
  159.      * Record allocated size of block and
  160.      * bound space with magic numbers.
  161.      */
  162.     if (nbytes <= 0x10000)
  163.         p->ov_size = nbytes - 1;
  164.     p->ov_rmagic = RMAGIC;
  165.     *((u_int *)((caddr_t)p + nbytes - RSLOP)) = RMAGIC;
  166. #endif /* RCHECK */
  167.     return ((char *)(p + 1));
  168. }
  169.  
  170. /*
  171.  * Allocate more memory to the indicated bucket.
  172.  */
  173. static
  174. morecore(bucket)
  175.     register bucket;
  176. {
  177.     register union overhead *op;
  178.     register int rnu;       /* 2^rnu bytes will be requested */
  179.     register int nblks;     /* become nblks blocks of the desired size */
  180.     register int siz;
  181.  
  182.     if (nextf[bucket])
  183.         return;
  184.     /*
  185.      * Insure memory is allocated
  186.      * on a page boundary.  Should
  187.      * make getpageize call?
  188.      */
  189.     op = (union overhead *)sbrk(0);
  190.     if ((long)op & 0x3ff)
  191.         sbrk(1024 - ((long)op & 0x3ff));
  192.     /* take 2k unless the block is bigger than that */
  193.     rnu = (bucket <= 8) ? 11 : bucket + 3;
  194.     nblks = 1 << (rnu - (bucket + 3));  /* how many blocks to get */
  195.     if (rnu < bucket)
  196.         rnu = bucket;
  197.     op = (union overhead *)sbrk(1 << rnu);
  198.     /* no more room! */
  199.     if ((long)op == -1)
  200.         return;
  201.     /*
  202.      * Round up to minimum allocation size boundary
  203.      * and deduct from block count to reflect.
  204.      */
  205.     if ((long)op & 7) {
  206.         op = (union overhead *)(((long)op + 8) &~ 7);
  207.         nblks--;
  208.     }
  209.     /*
  210.      * Add new memory allocated to that on
  211.      * free list for this hash bucket.
  212.      */
  213.     nextf[bucket] = op;
  214.     siz = 1 << (bucket + 3);
  215.     while (--nblks > 0) {
  216.         op->ov_next = (union overhead *)((caddr_t)op + siz);
  217.         op = (union overhead *)((caddr_t)op + siz);
  218.     }
  219. }
  220.  
  221. void
  222. free(cp)
  223.     char *cp;
  224. {   
  225.     register int size;
  226.     register union overhead *op;
  227.  
  228.     if (cp == NULL || debug < 5)
  229.         return;
  230.     op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
  231.     if (op->ov_magic != MAGIC) {
  232.         Debug("%s free() ignored\n",
  233.             op->ov_magic == OLDMAGIC ? "Duplicate" : "Bad");
  234.         return;                /* sanity */
  235.     }
  236.     op->ov_magic = OLDMAGIC;
  237. #ifdef RCHECK
  238.     if (op->ov_rmagic != RMAGIC) {
  239.         Debug("Range check failed, free() ignored\n");
  240.         return;
  241.     }
  242.     if (op->ov_index <= 13 &&
  243.         *(u_int *)((caddr_t)op + op->ov_size + 1 - RSLOP) != RMAGIC) {
  244.         Debug("Range check failed, free() ignored\n");
  245.         return;
  246.     }
  247. #endif /* RCHECK */
  248.     if (op->ov_index >= NBUCKETS)
  249.         return;
  250.     size = op->ov_index;
  251.     op->ov_next = nextf[size];
  252.     nextf[size] = op;
  253. #ifdef MSTATS
  254.     nmalloc[size]--;
  255. #endif /* MSTATS */
  256. }
  257.  
  258. /*
  259.  * When a program attempts "storage compaction" as mentioned in the
  260.  * old malloc man page, it realloc's an already freed block.  Usually
  261.  * this is the last block it freed; occasionally it might be farther
  262.  * back.  We have to search all the free lists for the block in order
  263.  * to determine its bucket: 1st we make one pass thru the lists
  264.  * checking only the first block in each; if that fails we search
  265.  * ``reall_srchlen'' blocks in each list for a match (the variable
  266.  * is extern so the caller can modify it).  If that fails we just copy
  267.  * however many bytes was given to realloc() and hope it's not huge.
  268.  */
  269. int reall_srchlen = 4;    /* 4 should be plenty, -1 =>'s whole list */
  270.  
  271. char *
  272. realloc(cp, nbytes)
  273.     char *cp; 
  274.     unsigned nbytes;
  275. {   
  276.     register u_int onb;
  277.     union overhead *op;
  278.     char *res;
  279.     register int i;
  280.     int was_alloced = 0;
  281.  
  282.     if (cp == NULL)
  283.         return (malloc(nbytes));
  284.     op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
  285.     if (op->ov_magic == MAGIC) {
  286.         was_alloced++;
  287.         i = op->ov_index;
  288.     } else {
  289.         /*
  290.          * Already free, doing "compaction".
  291.          *
  292.          * Search for the old block of memory on the
  293.          * free list.  First, check the most common
  294.          * case (last element free'd), then (this failing)
  295.          * the last ``reall_srchlen'' items free'd.
  296.          * If all lookups fail, then assume the size of
  297.          * the memory block being realloc'd is the
  298.          * smallest possible.
  299.          */
  300.         if ((i = findbucket(op, 1)) < 0 &&
  301.             (i = findbucket(op, reall_srchlen)) < 0)
  302.             i = 0;
  303.     }
  304.     onb = (1 << (i + 3)) - sizeof (*op) - RSLOP;
  305.     /* avoid the copy if same size block */
  306.     if (was_alloced &&
  307.         nbytes <= onb && nbytes > (onb >> 1) - sizeof(*op) - RSLOP)
  308.         return(cp);
  309.     if ((res = malloc(nbytes)) == NULL)
  310.         return (NULL);
  311.     if (cp != res)            /* common optimization */
  312.         bcopy(cp, res, (nbytes < onb) ? nbytes : onb);
  313.     if (was_alloced)
  314.         free(cp);
  315.     return (res);
  316. }
  317.  
  318. /*
  319.  * Search ``srchlen'' elements of each free list for a block whose
  320.  * header starts at ``freep''.  If srchlen is -1 search the whole list.
  321.  * Return bucket number, or -1 if not found.
  322.  */
  323. static
  324. findbucket(freep, srchlen)
  325.     union overhead *freep;
  326.     int srchlen;
  327. {
  328.     register union overhead *p;
  329.     register int i, j;
  330.  
  331.     for (i = 0; i < NBUCKETS; i++) {
  332.         j = 0;
  333.         for (p = nextf[i]; p && j != srchlen; p = p->ov_next) {
  334.             if (p == freep)
  335.                 return (i);
  336.             j++;
  337.         }
  338.     }
  339.     return (-1);
  340. }
  341.  
  342. #ifdef MSTATS
  343. /*
  344.  * mstats - print out statistics about malloc
  345.  * 
  346.  * Prints two lines of numbers, one showing the length of the free list
  347.  * for each size category, the second showing the number of mallocs -
  348.  * frees for each size category.
  349.  */
  350. mstats(s)
  351.     char *s;
  352. {
  353.     register int i, j;
  354.     register union overhead *p;
  355.     int totfree = 0,
  356.     totused = 0;
  357.  
  358.     Debug("Memory allocation statistics %s\nfree:\t", s);
  359.     for (i = 0; i < NBUCKETS; i++) {
  360.         for (j = 0, p = nextf[i]; p; p = p->ov_next, j++)
  361.             ;
  362.         Debug(" %d", j);
  363.         totfree += j * (1 << (i + 3));
  364.     }
  365.     Debug("\nused:\t");
  366.     for (i = 0; i < NBUCKETS; i++) {
  367.         Debug( " %d", nmalloc[i]);
  368.         totused += nmalloc[i] * (1 << (i + 3));
  369.     }
  370.     Debug("\n\tTotal in use: %d, total free: %d\n",
  371.         totused, totfree);
  372. }
  373. #endif /* MSTATS */
  374.  
  375. /* End of modified perl malloc.c */
  376.  
  377. char *
  378. calloc(nitems, itemsz)
  379. u_int nitems, itemsz;
  380. {
  381.     char *cp;
  382.  
  383.     cp = malloc(nitems * itemsz);
  384.     bzero(cp, nitems * itemsz);
  385.     return cp;
  386. }
  387.  
  388. /* These are needed for curses and other external linkage */
  389.  
  390. #undef free
  391.  
  392. char *
  393. cfree(p, n, s)
  394. char *p;
  395. u_int n, s;
  396. {
  397.     xfree(p);
  398.     return NULL;
  399. }
  400.  
  401. char *
  402. free(p)
  403. char *p;
  404. {
  405.     xfree(p);
  406.     return NULL;
  407. }
  408.  
  409. #else /* INTERNAL_MALLOC */
  410.  
  411. char *stackbottom;    /* set first thing in main() */
  412.  
  413. void
  414. xfree(cp)
  415. char *cp;
  416. {
  417.     extern char end[];
  418.  
  419.     if (cp >= end && cp < stackbottom && cp < (char *) &cp && debug < 5)
  420.     free(cp);
  421. }
  422.  
  423. #endif /* INTERNAL_MALLOC */
  424.  
  425. void
  426. free_vec(argv)
  427. char **argv;
  428. {
  429.     register int n;
  430.     if (!argv)
  431.     return;
  432.     for (n = 0; argv[n]; n++)
  433.     xfree(argv[n]);
  434.     xfree((char *)argv);
  435. }
  436.